package ebook.datastructure.typed.chapter8;

import com.google.gson.Gson;
import lombok.Data;
import lombok.NoArgsConstructor;
import utils.JsonFormatUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * description: <br>
 * createTime: 2020/8/1817:45 <br>
 *
 * @author zzh
 */
public class BinarySortedTree<T extends Comparable> {
    Node<T> root;

    public void addNode(T t) {
        Node node = new Node();
        node.setValue(t);
        addNode(node);
    }


    private void addNode(Node node) {
        if(root == null) {
            root = node;
        } else {
            linkedToNode(root, node);
        }
    }


    private void linkedToNode(Node<T> parent, Node node) {
        // 大于，等于放在右子节点
        if(parent.getValue().compareTo(node.getValue()) <= 0) {
            if(parent.getRight() == null) {
                parent.setRight(node);
            } else {
                linkedToNode(parent.getRight(), node);
            }
        } else {
            if(parent.getLeft() == null) {
                parent.setLeft(node);
            } else {
                linkedToNode(parent.getLeft(), node);
            }
        }
    }

    public void midVisitAll(Visitor<T> vistor) {
        midVisitAll(root, vistor);
    }


    private void midVisitAll(Node<T> node, Visitor<T> visstor) {
        if(node != null) {
            midVisitAll(node.getLeft(), visstor);
            visstor.visit(node.getValue());
            midVisitAll(node.getRight(), visstor);
        }
    }

    public void preVisitAll(Visitor<T> vistor) {
        preVisitAll(root, vistor);
    }


    private void preVisitAll(Node<T> node, Visitor<T> visstor) {
        if(node != null) {
            visstor.visit(node.getValue());
            preVisitAll(node.getLeft(), visstor);
            preVisitAll(node.getRight(), visstor);
        }
    }

    public void postVisitAll(Visitor<T> vistor) {
        postVisitAll(root, vistor);
    }


    private void postVisitAll(Node<T> node, Visitor<T> visstor) {
        if(node != null) {
            postVisitAll(node.getLeft(), visstor);
            postVisitAll(node.getRight(), visstor);
            visstor.visit(node.getValue());
        }
    }

    public List<Node<T>> find(T t) {
        List<Node<T>> result = new ArrayList<>();
        find(t, root, result);
        return result;
    }

    private List<Node<T>> find(T t, Node<T> node, List<Node<T>> result) {
        if(node == null) {
            return result;
        }
        int r = node.getValue().compareTo(t);
        switch (r) {
            case 1:
                find(t, node.getLeft(), result);
                return result;
            case 0:
                result.add(node);
            case -1:
                find(t, node.getRight(), result);
                return result;
            default:
                return result;
        }
    }

    public List<Node<T>> findMaxNodes() {
        List<Node<T>> result = new ArrayList<>();
        if(root != null) {
            Node rightNode = root;
            Node parentNode = null;
            while(rightNode.getRight() != null) {
                parentNode = rightNode;
                rightNode = parentNode.getRight();
                if(parentNode.getValue().equals(rightNode.getValue())) {
                    result.add(rightNode);
                } else {
                    result.clear();
                }
            }
            result.add(rightNode);
        }
        return result;
    }


    public List<Node<T>> findMinNodes() {
        List<Node<T>> result = new ArrayList<>();
        Node<T> currentNode = root;
        while(currentNode.getLeft() != null) {
            currentNode = currentNode.getLeft();
        }
        result.add(currentNode);
        result.addAll(find(currentNode.getValue(), currentNode.getRight(), new ArrayList<>()));
        return result;
    }

    public void deleteNodeByValue(T t) {
        Node<T> currentNode = root;
        Node<T> parentNode = null;
        while(currentNode != null) {
            int r = currentNode.getValue().compareTo(t);
            switch (r) {
                case 0:
                    //删除当前节点
                    Node<T> parent4NextNode = null;
                    Node<T> nextNode = currentNode.getRight();
                    while(nextNode != null) {
                        parent4NextNode= nextNode;
                        nextNode = nextNode.getLeft();
                    }
                    if(currentNode.getRight() == null) {
                        Node<T> leftNode = currentNode.getLeft();
                        if(parentNode == null) {
                            root = leftNode;
                        } else {
                            if(parentNode.getLeft() == currentNode) {
                                parentNode.setLeft(leftNode);
                            } else {
                                parentNode.setRight(leftNode);
                            }
                        }
                    } else {
                        // 找到右边的后继节点，判断是不是也等于要删除的值，等于则删除
                    }
                case -1:
                    currentNode = currentNode.getRight();
                    break;
                case 1:
                    currentNode = currentNode.getLeft();
            }
        }
    }


    public interface Visitor<T extends Comparable> {
        void visit(T t);
    }


    public static void main(String[] args) {
        BinarySortedTree<String> tree = new BinarySortedTree<>();
        tree.addNode("99");
        for (int i = 0; i < 100; i++) {
            tree.addNode(i + "");
        }
        tree.addNode("0");
        tree.addNode("1");
        tree.addNode("0");
        List result = tree.findMinNodes();
        System.out.println(JsonFormatUtil.formatJson(new Gson().toJson(tree)));;
        System.out.println(result.size());
        System.out.println("over");
    }
}
@Data
@NoArgsConstructor
class Node<T extends Comparable> {
    T value;
    Node<T> left;
    Node<T> right;
    Node<T> parent;


    public void setLeft(Node<T> left) {
        if(left != null) {
            left.setParent(this);
        }
        this.left = left;
    }


    public void setRight(Node<T> right) {
        if(right != null) {
            right.setParent(this);
        }
        this.right = right;
    }
}